package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class Code448_findDisappearedNumbers {

    public List<Integer> findDisappearedNumbers(int[] nums) {
        int[] arr = new int[nums.length+1];
        for (int i = 0; i < nums.length; i++) {
            arr[nums[i]] = 1;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == 0){
                res.add(i);
            }
        }
        return res;
    }

    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i] - 1;
            if (nums[i] != 0 && nums[temp] != 0){
                res.add(nums[temp]);
                nums[temp] = 0;
            }
        }
        for (int i = 0; i < res.size(); i++) {
            nums[res.get(i) - 1] = 0;
        }
        res.clear();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                res.add(i + 1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Code448_findDisappearedNumbers code448_findDisappearedNumbers = new Code448_findDisappearedNumbers();
        System.out.println(code448_findDisappearedNumbers.findDisappearedNumbers2(new int[]{4,3,2,7,8,2,3,1}));
    }

}
